1. Field of the Invention
This invention relates to the field of cryptographic systems.
2. Background Art
A cryptographic system is a system for sending a message from a sender to a receiver over a medium so that the message is “secure”, that is, so that only the intended receiver can recover the message. A cryptographic system (or cryptosystem) converts a message, referred to as “plaintext” into an encrypted format, known as “ciphertext.” The encryption is accomplished by manipulating or transforming the message using a “cipher key” or keys. The receiver “decrypts” the message, that is, converts it from ciphertext to plaintext, by reversing the manipulation or transformation process using the cipher key or keys. So long as only the sender and receiver have knowledge of the cipher key, such an encrypted transmission is secure.
A “classical” cryptosystem is a cryptosystem in which the enciphering information can be used to determine the deciphering information. To provide security, a classical cryptosystem requires that the enciphering key be kept secret and provided to users of the system over secure channels. Secure channels, such as secret couriers, secure telephone transmission lines, or the like, are often impractical and expensive.
A system that eliminates the difficulties of exchanging a secure enciphering key is known as “public key encryption.” By definition, a public key cryptosystem has the property that someone who knows only how to encipher a message cannot use the enciphering key to find the deciphering key without a prohibitively lengthy computation. An enciphering function is chosen so that once an enciphering key is known, the enciphering function is relatively easy to compute. However, the inverse of the encrypting transformation function is difficult, or computationally infeasible, to compute. Such a function is referred to as a “one way function” or as a “trap door function.” In a public key cryptosystem, certain information relating to the keys is public. This information can be, and often is, published or transmitted in a non-secure manner. Also, certain information relating to the keys is private. This information may be distributed over a secure channel to protect its privacy (or may be created by a local user to ensure privacy).
In the prior art, the trap door functions have been based on the difficult problem of factoring integers. The factoring scheme is based on the fact that it is easy to generate two very large prime numbers and multiply them together, but it is much more difficult to factor the result, that is, to determine the very large prime numbers from their product. The product can therefore be made public as part of the enciphering key without compromising the prime numbers that effectively constitute the deciphering key.
Another form of public key cryptosystem is referred to as an “elliptic curve” cryptosystem. An elliptic curve cryptosystem is based on points on an elliptic curve E defined over a finite field F. Elliptic curve cryptosystems rely for security on the difficulty in solving the discrete logarithm problem. An advantage of an elliptic curve cryptosystem is there is more flexibility in choosing an elliptic curve than in choosing a finite field. Nevertheless, elliptic curve cryptosystems have not been widely used in computer-based public key exchange systems due to their computational intensiveness. Computer-based elliptic curve cryptosystems are slow compared to other computer public key exchange systems. Elliptic curve cryptosystems are described in “A Course in Number Theory and Cryptography” (Koblitz, 1987, Springer-Verlag, New York).